package com.jack.leetcode.每日一题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 柱状图中最大的矩形 {

    public static void main(String[] args) {
        int[] heights = {2,1,5,6,2,3};
        System.out.println(largestRectangleArea(heights));
        int[] h = {1,1};
        System.out.println(largestRectangleArea(h));
        int[] a = {2,1,2};
        System.out.println(largestRectangleArea(a));
    }

    public static int largestRectangleArea(int[] heights) {
        int result = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        List<Integer> h = new ArrayList<>();
        int n = heights.length;
        for(int i = 0;i<n;i++){
            h.add(heights[i]);
        }
        h.add(0);
        for (int i = 0; i < n+1; i++) {
            while(!stack.isEmpty()&&h.get(stack.getLast()) > h.get(i)) {
                int last = stack.removeLast();
                if(stack.isEmpty()){
                    result = Math.max(result,i*h.get(last));
                }else{
                    result = Math.max(result,(i-stack.getLast()-1)*h.get(last));
                }
            }
            stack.add(i);
        }
        return result;
    }
}
